package com.beimihu.leetcode;

import java.util.Arrays;
import java.util.List;

public class MinimumTotal {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n + 1][n + 1];

        for(int i = n - 1; i >=0 ; i--){
            for(int j = 0 ; j <= i ;j++){
                dp[i][j] = Math.min( dp[i+1][j+1],dp[i+1][j]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }


    public int minimumTotalV2(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] memo = new int[n][n];

        for (int[] row : memo) {
            Arrays.fill(row, Integer.MIN_VALUE); // Integer.MIN_VALUE 表示没有计算过
        }
        return dfs(triangle, 0, 0, memo);
    }

    public static int dfs(List<List<Integer>> triangle,int i ,int j , int[][] memo){
        if(i == triangle.size() - 1){
            return memo[i][j];
        }

        if (memo[i][j] != Integer.MIN_VALUE){
            return memo[i][j];
        }

        return memo[i][j] = Math.min(dfs(triangle,i+1,j+1,memo),dfs(triangle,i+1,j,memo)) + triangle.get(i).get(j);


    }



}
